//https://leetcode.cn/problems/minimize-manhattan-distances/description/?envType=daily-question&envId=2024-07-09https://leetcode.cn/problems/minimize-manhattan-distances/description/?envType=daily-question&envId=2024-07-09
class Solution {
    struct MIN;
    struct MAX;

    /// 保留最大值和次最大值和它们的下标（v1最大）
    struct MAX {
        int v1 = INT_MIN, v2 = INT_MIN;
        int i1 = -1, i2 = -1;

        /// 添加元素和其下标
        void add(int val, int index) {
            if (val > v1) {
                v2 = v1;
                i2 = i1;
                v1 = val;
                i1 = index;
            } else if (val > v2) {
                i2 = index;
                v2 = val;
            }
        }
    };

    /// 保留最小值和次最小值和它们的下标（v1最小）
    struct MIN {
        int v1 = INT_MAX, v2 = INT_MAX;
        int i1 = -1, i2 = -1;

        /// 添加元素和其下标
        void add(int val, int index) {
            if (val < v1) {
                v2 = v1;
                i2 = i1;
                v1 = val;
                i1 = index;
            } else if (val < v2) {
                i2 = index;
                v2 = val;
            }
        }
    };

    /// 去除 index 后可能的最大曼哈顿距离
    int sub(const MAX &max1, const MIN &min1, int index) {
        int ans = INT_MIN;
        if (index != max1.i1) {
            if (index != min1.i1) ans = max1.v1 - min1.v1;
            else if (index != min1.i2) ans = max1.v1 - min1.v2;
        }
        if (index != max1.i2) {
            if (index != min1.i1) ans = max(ans, max1.v2 - min1.v1);
            else if (index != min1.i2) ans = max(ans, max1.v2 - min1.v2);
        }
        return ans;
    }

public:
    int minimumDistance(vector<vector<int>> &points) {
        // x = point[0] - point[1], y = point[0] + point[1]
        MAX max_x, max_y;
        MIN min_x, min_y;
        int i = 0;
        for (const auto &point: points) {
            int x = point[0] - point[1], y = point[0] + point[1];
            max_x.add(x, i);
            min_x.add(x, i);
            max_y.add(y, i);
            min_y.add(y, i);
            ++i;
        }
        int ans = INT_MAX;
        set<int> c{max_x.i1, max_x.i2, max_y.i1, max_y.i2, min_x.i1, min_x.i2, min_y.i1, min_y.i2};
        /// 逐个点判断
        for (auto i : c) {
            int t = max(sub(max_x, min_x, i), sub(max_y, min_y, i));
            if (t >= 0) ans = min(ans, t);
        }
        return ans;
    }
};